Computers and their peripheral devices are used for a wide variety of purposes including, data storage, communication, and document creation. Peripheral Component Interconnect (PCI) is a local bus standard that is commonly used to connect a computer with one or more peripheral devices. A PCI bus provides a high-speed connection with peripherals and can connect multiple peripheral devices to the host computer. The PCI bus typically connects several PCI cards and PCI bridges to the PCI host-bridge of a computer. As used herein and in the appended claims, the term “host device” refers to any device that is connected to one or more peripheral devices, preferably using a PCI connection.
Peripheral devices that use the PCI standard are used in most computers systems. Some examples of PCI-compliant devices include: modems, hard drives, sound cards, graphics cards, controller cards, and scanners. As shown in FIG. 1, PCI cards (101) are connected to a PCI bus (102). The PCI bus (102) serves the function of connecting each PCI card (101) to the core computer components, i.e., the central processing unit (CPU) (107) and memory (105). By controlling a PCI-to-PCI bridge (103) and a PCI host-bridge (106), the PCI bus (102) is connected to the system bus (104), whereby access to the CPU (107) is achieved. Complete functionality of most any PCI device (109) requires the processing power of the CPU (107) and available memory on the PCI card itself (101). While some methods of interfacing PCI cards (101) to the core computer components may differ slightly, the result is the same. That desired result is the complete functionality of several PCI devices (109), connected to PCI cards (101) through a corresponding bus line (108), operating at the same time.
The sizeable improvements in the speed and processing power of computers have led to an increase in the number of peripheral devices needing support and computing resources. Traditionally, the program responsible for allocation of PCI card and PCI bridge memory resources to PCI devices is part of the computer firmware, i.e., software stored in a ROM (read-only memory) that usually only operates when a computer is first booted up.
For example, most computers have a BIOS (basic input/output system) program that operates whenever the computer is booted. The BIOS is responsible for loading the operating system, verifying power and important utilities of hardware, including peripheral devices, and performing tests on memory to confirm read/write functionality. When a firmware environment such as BIOS allocates memory to PCI devices and bridges, the available memory becomes fragmented and the size of the remaining free memory segments decreases.
In addition to the memory being divided into smaller and less useful sizes, the size of the data structure containing the start and end addresses of all available memory segments grows unpredictably. This data structure is used for tracking each available memory segment. Consequently, the allocation of memory to PCI devices may fail in two possible scenarios. First, the size of the data structure (usually stored in the PCI host-bridge of a computer) responsible for keeping track of available memory segments may grow to a point beyond its allotted memory space. Data structures stored in a ROM (read-only memory) device have a very limited size. Second, the fragmented memory segments of a PCI card or PCI bridge do not meet the alignment and size requirements of one or more PCI devices.